package chart.树的遍历;

import chart.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/13 17:27
 * 后序遍历 - 左子树 -> 右子树 -> 根
 */
public class PostOrder {
    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<>(4, new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null)),
                new TreeNode(6, null, null));
        postOrderRecurse(root);
        System.out.println();
        postOrderIterate(root);
    }

    /**
     * 递归
     *
     * @param node 节点
     */
    static void postOrderRecurse(TreeNode<Integer> node) {
        if (node == null) return;
        if (node.left != null) postOrderRecurse(node.left);
        if (node.right != null) postOrderRecurse(node.right);
        System.out.print(node.val + " ");
    }

    /**
     * 迭代
     * 需要借助两个栈来实现
     * 先向栈中压入左子树，再压入右子树，那么先弹出来的是右子树
     *
     * @param root 节点
     */
    static void postOrderIterate(TreeNode<Integer> root) {
        if (root == null) return;
        Deque<TreeNode<Integer>> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new LinkedList<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            final TreeNode<Integer> pop = stack1.pop();
            stack2.push(pop.val);
            if (pop.left != null) stack1.push(pop.left);
            if (pop.right != null) stack1.push(pop.right);
        }
        stack2.forEach(v -> System.out.print(v + " "));
    }

    /**
     * 先根据 根 - 右 - 左 遍历树并将数据存入栈中
     * 再将数据从栈中弹出, 这样遍历的顺序就变成了 左 - 右 - 根
     */
    static void postOrderIteratorV2(TreeNode<Integer> node) {
        Stack<TreeNode<Integer>> stack1 = new Stack<>(), stack2 = new Stack<>();
        while (node != null || !stack1.isEmpty()) {
            if (node != null) {
                stack1.push(node);
                stack2.push(node);
                node = node.right;
            } else node = stack1.pop().left;
        }
        while (!stack2.isEmpty()) System.out.print(stack2.pop().val + " ");
    }

}
